//二叉搜索树：左子节点比父节点小，右子节点比父节点大
function BinarySearchTree (){
	var Node = function (key){
		this.key = key;
		this.left = null;
		this.right = null;
	};
	var root = null;
	this.insert = function (key){
		var node = new Node (key);
		if (root === null){
			root = node;
		}
		else{
			insertNode (root, node);
		}
	};
	var insertNode = function (root, node){
		if (node.key < root.key){
			if (root.left === null){
				root.left = node;
			}
			else{
				insertNode (root.left, node);
			}
		}
		else{
			if (root.right === null){
				root.right = node;
			}
			else{
				insertNode (root.right, node);
			}
		}
	};
	//先序遍历所有节点,callback->获取到节点后的回调函数
	this.preOrder = function (){
		preOrder (root);
	};
	var preOrder = function (node){
		if (node != null){
			console.log (node.key);
			preOrder (node.left);
			preOrder (node.right);
		}
	};
	//树中的最小值：最左侧
	this.min = function (){
		return minNode (root);
	};
	var minNode = function (root){
		if (node){
			while (node && node.left != null){
				node = node.left;
			}
			return node.key;
		}
		return null;
	};
	this.hight = function (){
		return getHight(root);
	};
	var getHight = function (root){
		var left = 0,
			right = 0;
		if (root == null) return 0;
		else{
			left = getHight (root.left) + 1;
			right = getHight (root.right) + 1;
			return left >= right? left :right;
		}
		
	};
}

var tree  = new BinarySearchTree();
tree.insert(8);
tree.insert(9);
tree.insert(4);
tree.insert(2);
tree.preOrder();
var hight = tree.hight();
console.log(hight);